
/////////////////////////////////////////////////////////////////////////////////
//
//  线性表 ： http://c.biancheng.net/view/3334.html 引用传递
//
/////////////////////////////////////////////////////////////////////////////////

#include<iostream>

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef struct Table{
    int * head;     // 声明了一个名为head的长度不确定的数组，也叫 动态数组
    int length;     // 记录当前顺序表的长度
    int size;       // 记录顺序表分配的存储容量
} Table ;

Table table_create()
{
    Table table;
    table.size = LIST_INIT_SIZE;
    int *head = (int *)malloc(table.size * sizeof(int));
    table.head = head;
    table.length = 0;
    return table;
}

// 在 第index 位置 插入 target 元素， index开始所有元素后移（反向，从尾部移动） 。
int table_insert(Table &t, int index, int target)
{
    if (index < 0|| index >t.length)
    {
        return -1;
    }


    if(t.length >= t.size)
    {
        int newSize = t.size + LISTINCREMENT;
        t.head = (int *)realloc(t.head,newSize*sizeof(int) );
        t.size = newSize;
    }

    for (int i = t.length; i > index;i--)
    {
        t.head[i] = t.head[i - 1];
    }
    t.head[index] = target;
    t.length++;
    return 0;
}

int table_remove(Table &t, int index, int *target=nullptr)
{
    if (index < 0|| index >t.length-1)
    {
        return -1;
    }

    if(target)
    {
        *target = t.head[index];
    }

    for (; index < t.length - 1;index++)
    {
        t.head[index] = t.head[index + 1];
    }
    t.length--;

    return 0;
}

int table_find(Table &t, int target)
{
    int pos = -1;

    for (int i = 0; i < t.length; i++)
    {
        if (t.head[i] == target)
        {
            pos = i;
            break;
        }
    }
    return pos;
}

void showList(Table &lst)
{
    for (int i = 0; i < lst.length; i++)
    {
        std::cout << lst.head[i] << " ";
    }
    std::cout << std::endl;
}

int main()
{
    Table t = table_create();
    for (int i = 0; i < 10;i++)
    {
        table_insert(t,i,i);
    }
    showList(t);

    int target = 5;
    int pos = table_find(t, target);
    std::cout << target << " at " << pos <<std::endl;

    int index = 5;
    table_remove(t,index, &target);
    std::cout << target << " is removed " <<std::endl;
    showList(t);

    return EXIT_SUCCESS;
}

